package com.myutil.graph;

public class IntQueue {
	private class Elem{
		public int[] values;
		public Elem next;
		
		public Elem(int[] values) {
			this.values = values;
			this.next=null;
		}
	}
	
	public int length;//队列长度
	private int step;//分配空间步长
	private Elem last;//队尾
	private Elem first;//队首
	private int firstIndex;//队首起点
	private int lastIndex;//队尾终点
	
	public IntQueue() {
		init(2);
	}
	public IntQueue(int capacity) {
		init(capacity);
	}
	
	/**
	 * 初始化
	 */
	private void init(int step) {
		this.length=0;
		this.step=step;
		this.last=new Elem(new int[this.step]);
		this.lastIndex=0;
		this.first=this.last;
		this.firstIndex=0;
	}
	
	/**
	 * 队尾加入一个int元素值
	 * @param value int
	 */
	public void add(int value){
		if(lastIndex>=this.last.values.length){
			this.step*=2;
			Elem newOne=new Elem(new int[step]);
			this.last.next=newOne;
			this.last=newOne;
			this.lastIndex=0;
		}
		last.values[this.lastIndex]=value;
		this.lastIndex++;
		this.length++;
	}
	
	/**
	 * 移除队首元素，返回该元素值，如果无效则返回-1
	 * @return int
	 */
	public int remove(){
		if(this.length<1){
			return -1;
		}
		if(firstIndex>=this.first.values.length){
			Elem de=this.first;
			this.first=this.first.next;
			de.values=null;
			de.next=null;
			this.firstIndex=0;
		}
		this.length--;
		int result=this.first.values[this.firstIndex];
		this.firstIndex++;
		return result;
	}
	
	/**
	 * 清空
	 */
	public void clear() {
		//置空，垃圾回收机制自己回收去
		Elem de;
		while(this.first!=null){
			de=this.first;
			this.first=this.first.next;
			de.values=null;
			de.next=null;
		}
		//分配空间
		init(2);
	}
	
	/**
	 * 销毁
	 */
	public void destroy() {
		//置空，垃圾回收机制自己回收去
		Elem de;
		while(this.first!=null){
			de=this.first;
			this.first=this.first.next;
			de.values=null;
			de.next=null;
		}
	}
	
	/**
	 * 判断队列空,true为队列空
	 * @return boolean
	 */
	public boolean isEmpty() {
		if(this.length<1) return true;
		else return false;
	}
	
	/** 返回队列空间所占大小,字节数
	 * @return int
	 */
	public int size() {
		int size=0;
		Elem cur=this.first;
		while(cur!=null){
			size+=cur.values.length*4;
			cur=cur.next;
		}
		return size;
	}
}
